package demo1;

public class MySingleList implements List{

    //节点
    //因为节点是一个独立的对象，使用内部类来实现节点

    static class Node
    {
        public   int data; //用于存放数据
        public Node next; //用于存放地址

        public Node(int data) {
            this.data = data;
        }
    }

    public Node head;  //创建指向链表头结点的指针


    @Override
    public void addFirst(int data) {
        //头插法
        //先找到链表，再进行头插
        if(head == null){
            head = new Node(data);
        }else {
            Node cur = new Node(data);
            cur.next = head;
            head = cur;
        }
    }

    @Override
    public void addLast(int data) {
        //尾插法：
       //先找到尾节点
        //头节点是否为空，
        if(head == null){
            head = new Node(data);
        }else {
            Node cur = head;
            //找到链表中最后一个节点
            while (cur.next!=null){
                cur = cur.next;
            }
            //找到最后一个节点后，进行尾插
            cur.next = new Node(data);
        }
    }

    @Override
    public void addIndex(int index, int data) {
        //需要判断index的值是否合法。
        if(index>size()||index<0){
            System.out.println("index的值不合法");
            return;
        }
           if(index ==0) {
               //如果index处于顺序表的头节点处
               addFirst(data);
               return;
           }
            //如果index处于顺序表末尾的后一位
            if (index ==size()){
                //则直接调用addLast方法即可
                addLast(data);
                return ;
                }
            if(index>0&&index<size()){
                //进行中间插入，需要找到插入位置的前一个节点，找到插入位置
                Node cur = head;
                while(index>1){
                    cur = cur.next;
                    index--;
                }
                //此为插入位置的前一个节点
                Node prev = cur;
                //此为插入位置的节点
                cur = prev.next;
                //创建一个新的节点并插入：
                Node cur2 = new Node(data);
                cur2.next =cur;
                prev.next = cur2;
                return;
            }
            }


    @Override
    public boolean contains(int key) {
        //判断链表中是否包含关键字
        Node cur = head;
        while (cur!= null){
            if (cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head ==null){
            return;
        }
        //移除第一次出现的关键字key
        Node cur = head;
        Node prev = cur;
        while (cur!=null){
            if(cur.data ==key){
                //如果此时cur节点为头节点
             if(cur ==head){
                 head = head.next;
                 cur = null;
                 return;
             }else {
                 //如果此时cur节点是非头节点
                 prev.next = cur.next;
                 return;
             }
            }
            prev = cur;
            cur = cur.next;
        }
    }

    @Override
    public void removeAllkey(int key) {
        if (head == null) {
            return;
        }
        //移除链表中所有的关键字key
        //不采用多重循环，而只采用一次循环，将所有的关键字移除
        Node cur = head;
        Node prev = head;
        while (cur != null) { //开始遍历所有的节点
            if (cur.data == key) {
                //需要先进行判断，此节点是否为头节点
                if (cur == head) {
                    head = head.next;
                    cur = cur.next;
                    prev = prev.next;
                }
                //如果不为头结点
                else {
                    //则删除所有对此节点的引用
                    cur = cur.next;
                    prev.next = cur;

                }
                //这样的思想过于麻烦
                //当cur.data!=null时
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
    }
    @Override
    public int  size() {
       int count = 0;
       Node cur = head;
       while (cur!=null){
           count++;
           cur = cur.next;

       }
       return count;
    }

    @Override
    public void clear() {
           //清空链表
        Node cur= head;
        while (cur!=null){
            Node curN = cur; //将当前节点赋给curN
            cur = cur.next;    //指针后移
            curN.next  = null; //将当前节点的next值置为空
        }
     //最后头结点再置为null
        head = null;
    }

    @Override
    public void display() {
       Node cur  = head;
       while (cur!=null){
           System.out.print(cur.data+" ");
           cur =cur.next;
       }
    }
}
